package main

import "fmt"

// 如何求一个字符串的所有排列
// 引申：如何去掉重复的排列

func main() {
	permutationStr("abc")
	permutationStr2("aba")
}

func permutationStr(s string) {
	permutation([]rune(s), 0)
}

func swapRune(str []rune, i, j int) {
	str[i], str[j] = str[j], str[i]
}

func permutation(str []rune, start int) {
	if str == nil {
		return
	}

	if start == len(str)-1 {
		fmt.Println(string(str))
	} else {
		for i := start; i < len(str); i++ {
			swapRune(str, start, i)
			permutation(str, start+1)
			swapRune(str, start, i)
		}
	}
}

func isDuplicate(str []rune, begin, end int) bool {
	for i := begin; i < end; i++ {
		if str[i] == str[end] {
			return false
		}
	}
	return true
}

func permutationStr2(s string) {
	permutation2([]rune(s), 0)
}

func permutation2(str []rune, start int) {
	if start == len(str)-1 {
		fmt.Println(string(str))
	} else {
		for i := start; i < len(str); i++ {
			if !isDuplicate(str, start, i) {
				continue
			}
			swapRune(str, start, i)
			permutation2(str, start+1)
			swapRune(str, start, i)
		}
	}
}
